home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / simulato / v2_3_mc6.tz / v2_3_mc6 / testfiles / treefnd1.asm < prev    next >
Assembly Source File  |  1994-05-02  |  11KB  |  257 lines
  1. ************************************************************
  2. *
  3. * CDA 3101. FALL '92.
  4. * Assn #2.
  5. * Inserts, searches, prints elements in a binary
  6. * search tree.  Program prompts the user for a command
  7. * (I,S,P,E) and a single digit (0-9) and either inserts
  8. * the value in tree, searches for the value in tree,
  9. * prints the tree, or exits.
  10. *
  11. *
  12. ************************************************************
  13. *
  14. *********************************
  15. *  ANCHOR 
  16. *********************************
  17. *
  18.             ORG     $2000
  19. ANCHOR      DS.L    1
  20. *
  21. *********************************
  22. *  MESSAGES  
  23. *********************************
  24. *
  25. INTEGER     DC.B    'Integer '      ;for printing purposes
  26. PRN_VAL     DS.B    1               ;bogus location for word operations
  27. VALUE       DS.B    1               ;integer value is stored here
  28.             DC.B    ':  ',0
  29. INSERTED    DC.B    ' has been inserted.',13,10,13,10,0
  30. EXISTS      DC.B    ' already exists in this tree.',13,10,0
  31. FOUND       DC.B    ' has been found in this tree.',13,10,13,10,0
  32. NOT         DC.B    ' could not be found in this tree.',13,10,0
  33. ERROR       DC.B    'Only enter valid commands (I,S,P, or E)',13,10,0
  34. EMPTY       DC.B    'Tree is empty.',13,10,0
  35. PROMPT1     DC.B    'Enter command (I,S,P, or E) and integer (0-9) ...',13,10,0
  36. PRN_PROMPT  DC.B    'Traversal in preorder ...',13,10,0
  37. CHAR_RTN    DC.B    13,10,0         ;used only to make output more aesthetic
  38. *
  39. *********************************************
  40. *
  41. *         M A I N     P R O G R A M   
  42. *
  43. *********************************************
  44. *
  45.             ORG         $1000
  46. MAIN        CLR.L       D0                  ;
  47.             MOVE.L      D0,ANCHOR           ;initialize ANCHOR
  48. START       MOVEA.L     #PROMPT1,A0         ;prompt the user
  49.             JSR         WriteString         ;
  50.             MOVEA.L     #$6000,A0           ;
  51.             JSR         ReadString          ;
  52.             MOVEA.L     #$6000,A0           ;
  53.             JSR         FIND_INFO           ;get command and integer value
  54.             CMP.B       #'I',D0             ;if command = I, jump to INSERT
  55.             BNE         SECOND
  56.             JSR         INSERT
  57.             BRA         START
  58. SECOND      CMP.B       #'S',D0             ;if command = S, jump to SEARCH
  59.             BNE         THIRD
  60.             JSR         SEARCH
  61.             BRA         START
  62. THIRD       CMP.B       #'P',D0             ;if command = P, jump to PRINTOUT
  63.             BNE         FOURTH
  64.             JSR         PRINTOUT
  65.             BRA         START
  66. FOURTH      CMP.B       #'E',D0             ;if command = E, jump to EXIT
  67.             BNE         LAST
  68.             JSR         EXIT
  69. LAST        MOVEA.L     #ERROR,A0           ;if command is invalid, print
  70.             JSR         WriteString         ;  error message
  71.             BRA         START
  72. *
  73. ********************************************
  74. *
  75. *  SUBROUTINE:      F I N D _ I N F O
  76. *
  77. ********************************************
  78. *
  79. FIND_INFO   MOVEA.L     A0,A3               ;copy the register
  80. HEREF       CMP.B       #$20,(A3)           ;is A3 pointing to a blank space?
  81.             BNE         CONTF               ;  if not, this is the command
  82.             LEA         1(A3),A3            ;  if so, increment A3 and check
  83.             BRA         HEREF
  84. CONTF       MOVE.B      (A3),D0             ;put command into D0
  85.             JSR         LOW_TO_UP           ;change from lower to upper case
  86.             CMP.B       #'I',D0             ;if the command is an I or an S,
  87.             BEQ         GET_NUM             ;  then look for integer value
  88.             CMP.B       #'S',D0             ;  needed
  89.             BEQ         GET_NUM             ;if command is no I or S, return
  90.             BRA         RETURNF
  91. GET_NUM     LEA         1(A3),A3            ;increment A3
  92.             CMP.B       #$20,(A3)           ;is A3 pointing to a blank space?
  93.             BNE         GOT_NUM             ;  if not, this is the int val
  94.             BRA         GET_NUM             ;  if so, go back
  95. GOT_NUM     MOVE.B      (A3),VALUE          ;put integer value into VALUE
  96. RETURNF     RTS
  97. *
  98. ********************************************
  99. *
  100. *  SUBROUTINE:    L O W _ T O _ U P 
  101. *
  102. ********************************************
  103. *
  104. LOW_TO_UP   CMP.B       #'i',D0             ;only look for valid commands
  105.             BNE         1$                  ;  in lower case to convert to 
  106.             MOVE.B      #'I',D0             ;  upper case
  107.             BRA         RETURNL
  108. 1$          CMP.B       #'s',D0
  109.             BNE         2$
  110.             MOVE.B      #'S',D0
  111.             BRA         RETURNL
  112. 2$          CMP.B       #'p',D0
  113.             BNE         3$
  114.             MOVE.B      #'P',D0
  115.             BRA         RETURNL
  116. 3$          CMP.B       #'e',D0
  117.             BNE         RETURNL
  118.             MOVE.B      #'E',D0
  119. RETURNL     RTS
  120. *
  121. ********************************************
  122. *
  123. *  SUBROUTINE:      I N S E R T
  124. *
  125. ********************************************
  126. *
  127. INSERT      MOVEA.L     #CHAR_RTN,A0        ;aesthetics
  128.             JSR         WriteString
  129.             MOVEA.L     #INTEGER,A0         ;message 'integer' + integer val
  130.             JSR         WriteString
  131.             MOVE.L      #10,D0              ;need 10 bytes for new node
  132.             JSR         malloc
  133.             MOVE.L      #0,(A0)             ;initialize new node with null
  134.             MOVE.W      #$FF,4(A0)          ;  left and right pointers and
  135.             MOVE.L      #0,6(A0)            ;  and $FF for data
  136.             CMP.L       #0,(ANCHOR).L       ;is the ANCHOR null?
  137.             BNE         CONTI               ;  if not, branch
  138.             MOVE.L      A0,ANCHOR           ;  if so, give ANCHOR its value
  139.             MOVE.W      PRN_VAL,4(A0)       ;    and put the value in
  140.             BRA         DONEI
  141. CONTI       MOVEA.L     ANCHOR,A4           ;copy the anchor
  142. HEREI       MOVE.W      4(A4),D3            ;
  143.             CMP.B       VALUE,D3            ;is the value already in the tree
  144.             BEQ         EXISTI              ;  if so, branch
  145.             BMI         RIGHTI              ;else, is value < data field
  146. LEFTI       CMPI.L      #0,(A4)             ;if the left pointer is null
  147.             BEQ         LINSERT             ;  branch
  148.             MOVEA.L     (A4),A4             ;else, go down to left node
  149.             BRA         HEREI               ;  and check again
  150. LINSERT     MOVE.L      A0,(A4)             ;make left pointer = new node
  151.             MOVEA.L     (A4),A4             ;move to new node
  152.             MOVE.W      PRN_VAL,4(A4)       ;put value into data field
  153.             BRA         DONEI
  154. RIGHTI      CMPI.L      #0,6(A4)            ;if the right pointer is null
  155.             BEQ         RINSERT             ;  branch
  156.             MOVEA.L     6(A4),A4            ;else, go down to right node
  157.             BRA         HEREI               ;  and check again
  158. RINSERT     MOVE.L      A0,6(A4)            ;make right pointer = new node
  159.             MOVEA.L     6(A4),A4            ;move to new node
  160.             MOVE.W      PRN_VAL,4(A4)       ;put value into data field
  161.             BRA         DONEI
  162. EXISTI      MOVEA.L     #EXISTS,A0          ;message 
  163.             JSR         WriteString
  164.             BRA         RETURNI
  165. DONEI       MOVEA.L     #INSERTED,A0        ;message
  166.             JSR         WriteString
  167. RETURNI     RTS
  168. *
  169. ********************************************
  170. *
  171. *  SUBROUTINE:    S E A R C H
  172. *
  173. ********************************************
  174. *
  175. SEARCH      MOVEA.L     #CHAR_RTN,A0        ;aesthetics
  176.             JSR         WriteString
  177.             MOVEA.L     #INTEGER,A0         ;message
  178.             JSR         WriteString
  179.             CMP.L       #0,ANCHOR           ;is the ANCHOR null
  180.             BEQ         EMPTYS              ;  if so, branch (tree empty)
  181.             MOVEA.L     ANCHOR,A4           ;  if not, copy ANCHOR
  182. HERES       MOVE.W      4(A4),D3
  183.             CMP.B       VALUE,D3            ;is value = data field
  184.             BEQ         FOUNDS              ;  if so, element is found
  185.             BMI         RIGHTS              ;is value < data field
  186. LEFTS       CMPI.L      #0,(A4)             ;are you at a leaf node
  187.             BEQ         NOTS                ;  if so, element not found
  188.             MOVEA.L     (A4),A4             ;  if not, move to left node
  189.             BRA         HERES               ;    and check again
  190. RIGHTS      CMPI.L      #0,6(A4)            ;are you at a leaf node
  191.             BEQ         NOTS                ;  if so, element not found
  192.             MOVEA.L     6(A4),A4            ;  if not move to right node
  193.             BRA         HERES               ;    and check again
  194. EMPTYS      MOVEA.L     #EMPTY,A0           ;message
  195.             JSR         WriteString
  196.             BRA         RETURNS
  197. FOUNDS      MOVEA.L     #FOUND,A0           ;message
  198.             JSR         WriteString
  199.             BRA         RETURNS
  200. NOTS        MOVEA.L     #NOT,A0             ;message
  201.             JSR         WriteString
  202. RETURNS     RTS
  203. *
  204. ********************************************
  205. *
  206. *  SUBROUTINE:   P R I N T O U T 
  207. *
  208. ********************************************
  209. *
  210. PRINTOUT    LINK        A6,#-40             ;give stack max space needed
  211.             MOVEA.L     #CHAR_RTN,A0        ;aesthetics
  212.             JSR         WriteString
  213.             MOVEA.L     #PRN_PROMPT,A0      ;message
  214.             JSR         WriteString
  215.             CMP.L       #0,ANCHOR           ;is ANCHOR null
  216.             BEQ         EMPTYP              ;  if so, tree is empty
  217.             MOVEA.L     ANCHOR,A4           ;  if not, copy ANCHOR
  218.             MOVE.L      #$FF,-(A7)          ;initialize end of stack
  219. HEREP       MOVE.W      4(A4),D0            ;preorder-print element first
  220.             JSR         WriteChar
  221.             MOVE.W      #$20,D0             ;aesthetics - spaces between
  222.             JSR         WriteChar
  223.             CMP.L       #0,6(A4)            ;is the right child null
  224.             BEQ         CONTP               ;  if so, no stack operation
  225.             MOVE.L      6(A4),-(A7)         ;  if not, put address on stack
  226. CONTP       CMP.L       #0,(A4)             ;is the left child null
  227.             BEQ         CHECK               ;  if so, branch
  228.             MOVEA.L     (A4),A4             ;  if not, move to left child
  229.             BRA         HEREP
  230. CHECK       CMP.L       #$FF,(A7)           ;is this the end of the stack
  231.             BEQ         END                 ;  if so, you're done
  232.             MOVEA.L     (A7)+,A4            ;  if not, get address from stack
  233.             BRA         HEREP
  234. EMPTYP      MOVEA.L     #EMPTY,A0           ;message
  235.             JSR         WriteString
  236. END         MOVEA.L     #CHAR_RTN,A0        ;aesthetics
  237.             JSR         WriteString
  238.             MOVEA.L     #CHAR_RTN,A0        ;aesthetics
  239.             JSR         WriteString
  240.             UNLK        A6
  241.             RTS
  242. *
  243. ********************************************
  244. *
  245. *   E N D    O F    P R O G R A M 
  246. *
  247. ********************************************
  248. *
  249. EXIT        MOVE        #228,D7             ;
  250.             TRAP        #14                 ;
  251.             NOLIST
  252.             DC.W        0
  253.             INCLUDE     "samples.asm"
  254.             LIST
  255.             END
  256.  
  257.